#include <iostream>
#include <cassert>
using namespace std;
// 142.环形链表II
// 给你一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x): val(x), next(nullptr) {}
    ListNode(int x,ListNode* next):val(x),next(next) {}
};

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow, *fast;
        slow = fast = head;
        while(fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
            if(slow == fast) {  // 有环，两指针到达首次相遇点
                slow = head;    // slow从head开始走，fast在相遇点
                while(slow != fast) {
                    slow = slow->next;
                    fast = fast->next;
                }
                return slow;
            }
        }
        return nullptr; // 退出while循环还没返回，则表示没有环
    }
};

int main() {
    // 给定链表 1，表示1个元素，无环
    ListNode* node5 = new ListNode(1);
    ListNode* firstMeet = Solution().detectCycle(node5);
    if(firstMeet != nullptr)
        cout << firstMeet->val << endl;

    // 给定链表 1->2->1，pos = 0
    ListNode* node6 = new ListNode(1);
    ListNode* node7 = new ListNode(2);
    node6->next = node7; node7->next = node6;
    firstMeet = Solution().detectCycle(node6);
    if(firstMeet != nullptr)
        cout << firstMeet->val << endl;

    // 给定链表 3->2->0->-4->2，返回索引1
    ListNode* node4 = new ListNode(-4);
    ListNode* node3 = new ListNode(0,node4);
    ListNode* node2 = new ListNode(2,node3);
    ListNode* node1 = new ListNode(3,node2);
    node4->next = node2;

    firstMeet = Solution().detectCycle(node1);
    cout << firstMeet->val << endl;





    return 0;
}
